#ifndef HASHSET_IMPL_H_
#define HASHSET_IMPL_H_
#define IMPL_QUAL_HASHSET(TYPE, HASH, EQ, QUAL) \
QUAL ctl_res_##TYPE ctl_hashset_##TYPE##_##HASH##_##EQ##_iter_data(ctl_hashset_##TYPE##_##HASH##_##EQ##_iter iter) { \
  ctl_res_##TYPE res = {0}; \
  res.ec = EOK; \
  CHECK_COND_RET_RES(iter.node != NULL, ENULLPTR, res); \
  TYPE##_copy(&(res.value), &(iter.node->value)); \
  return res; \
} \
QUAL ctl_res_ctl_hashset_##TYPE##_##HASH##_##EQ##_iter ctl_hashset_##TYPE##_##HASH##_##EQ##_iter_next(ctl_hashset_##TYPE##_##HASH##_##EQ##_iter iter) { \
  ctl_res_ctl_hashset_##TYPE##_##HASH##_##EQ##_iter res = {0}; \
  res.ec = EOK; \
  if (iter.node == NULL) { \
    res.ec = ENOTFOUND; \
    return res; \
  } \
  size_t bucket_idx = iter.bucket_idx; \
  size_t bucket_size = iter.bucket_size; \
  ctl_hashset_##TYPE##_##HASH##_##EQ##_node** buckets = iter.buckets; \
  ctl_hashset_##TYPE##_##HASH##_##EQ##_node* node = NULL; \
  if (iter.node->next != NULL) { \
      res.value.buckets = buckets; \
      res.value.bucket_idx = bucket_idx; \
      res.value.bucket_size = bucket_size; \
      res.value.node = iter.node->next; \
      res.ec = EOK; \
      return  res; \
  } else { \
    bucket_idx++; \
    for (; bucket_idx < bucket_size; bucket_idx++) { \
      node = buckets[bucket_idx]; \
      if (node) { \
        res.value.buckets = buckets; \
        res.value.bucket_idx = bucket_idx; \
        res.value.bucket_size = bucket_size; \
        res.value.node = node; \
        res.ec = EOK; \
        return res; \
      } \
    } \
  } \
  res.ec = ENOTFOUND; \
  return res; \
} \
QUAL ctl_res_ctl_hashset_##TYPE##_##HASH##_##EQ##_iter ctl_hashset_##TYPE##_##HASH##_##EQ##_begin(ctl_hashset_##TYPE##_##HASH##_##EQ* ht) { \
  ctl_res_ctl_hashset_##TYPE##_##HASH##_##EQ##_iter res = {0}; \
  res.ec = EOK; \
  size_t bucket_idx = 0U; \
  size_t bucket_size = ht->bucket_size; \
  ctl_hashset_##TYPE##_##HASH##_##EQ##_node** buckets = ht->buckets; \
  ctl_hashset_##TYPE##_##HASH##_##EQ##_node* node = NULL; \
  for (bucket_idx = 0U; bucket_idx < bucket_size; bucket_idx++) { \
    node = buckets[bucket_idx]; \
    if (node) { \
        res.value.buckets = buckets; \
        res.value.bucket_idx = bucket_idx; \
        res.value.bucket_size = bucket_size; \
        res.value.node = node; \
        res.ec = EOK; \
        return res; \
    } \
  } \
  res.ec = ENOTFOUND; \
  return res; \
} \
QUAL ctl_res_void _ctl_hashset_##TYPE##_##HASH##_##EQ##_new_node(ctl_hashset_##TYPE##_##HASH##_##EQ##_node** node, TYPE value) { \
  ctl_res_void res = {0}; \
  res.ec = EOK; \
  *node = (ctl_hashset_##TYPE##_##HASH##_##EQ##_node*)malloc(sizeof(ctl_hashset_##TYPE##_##HASH##_##EQ##_node)); \
  CHECK_COND_RET_RES(*node != NULL, EOOM, res); \
  (*node)->next = NULL; \
  TYPE##_ctor(&((*node)->value)); \
  TYPE##_copy(&((*node)->value), &value); \
  return res; \
} \
QUAL ctl_res_void _ctl_hashset_##TYPE##_##HASH##_##EQ##_free_node(ctl_hashset_##TYPE##_##HASH##_##EQ##_node* node) { \
  ctl_res_void res = {0}; \
  res.ec = EOK; \
  TYPE##_dtor(&(node->value)); \
  free(node); \
  node = NULL; \
  return res; \
} \
QUAL void _ctl_hashset_##TYPE##_##HASH##_##EQ##_push_front_node(ctl_hashset_##TYPE##_##HASH##_##EQ* ht, size_t idx, ctl_hashset_##TYPE##_##HASH##_##EQ##_node* node) { \
  ctl_hashset_##TYPE##_##HASH##_##EQ##_node** head = ht->buckets + idx; \
  if (*head) { \
    node->next = *head; \
    *head = node; \
  } else { \
    *head = node; \
  } \
} \
QUAL void _ctl_hashset_##TYPE##_##HASH##_##EQ##_push_front(ctl_hashset_##TYPE##_##HASH##_##EQ* ht, size_t idx, TYPE value) { \
  ctl_hashset_##TYPE##_##HASH##_##EQ##_node* node = NULL; \
  _ctl_hashset_##TYPE##_##HASH##_##EQ##_new_node(&node, value); \
  _ctl_hashset_##TYPE##_##HASH##_##EQ##_push_front_node(ht, idx, node); \
} \
QUAL ctl_hashset_##TYPE##_##HASH##_##EQ##_node* _ctl_hashset_##TYPE##_##HASH##_##EQ##_pop_front_node(ctl_hashset_##TYPE##_##HASH##_##EQ* ht, size_t idx) { \
  ctl_hashset_##TYPE##_##HASH##_##EQ##_node** head = ht->buckets + idx; \
  ctl_hashset_##TYPE##_##HASH##_##EQ##_node* old_head = *head; \
  if (old_head == NULL) {  \
    return NULL; \
  } \
  *head = old_head->next; \
  return old_head; \
} \
QUAL ctl_res_void _ctl_hashset_##TYPE##_##HASH##_##EQ##_pop_front(ctl_hashset_##TYPE##_##HASH##_##EQ* ht, size_t idx) { \
  ctl_res_void res = {0}; \
  res.ec = EOK; \
  ctl_hashset_##TYPE##_##HASH##_##EQ##_node* old_head = _ctl_hashset_##TYPE##_##HASH##_##EQ##_pop_front_node(ht, idx); \
  if (old_head) { \
    _ctl_hashset_##TYPE##_##HASH##_##EQ##_free_node(old_head); \
  } \
  return  res; \
} \
QUAL ctl_res_void _ctl_hashset_##TYPE##_##HASH##_##EQ##_allocate(ctl_hashset_##TYPE##_##HASH##_##EQ* ht, size_t bucket_size) { \
  ctl_res_void res = {0}; \
  res.ec = EOK; \
  ht->bucket_size = bucket_size; \
  ctl_hashset_##TYPE##_##HASH##_##EQ##_node** buckets = (ctl_hashset_##TYPE##_##HASH##_##EQ##_node**)malloc( \
    sizeof(ctl_hashset_##TYPE##_##HASH##_##EQ##_node*) * bucket_size); \
  CHECK_COND_RET_RES(buckets != NULL, EOOM, res); \
  ht->buckets = buckets; \
  size_t bucket_idx = 0U; \
  for (bucket_idx = 0U; bucket_idx < bucket_size; bucket_idx++) { \
    ht->buckets[bucket_idx] = NULL; \
  } \
  return res; \
} \
QUAL int _ctl_hashset_##TYPE##_##HASH##_##EQ##_should_grow(ctl_hashset_##TYPE##_##HASH##_##EQ* ht) { \
  return ht->size == ht->bucket_size; \
} \
QUAL int _ctl_hashset_##TYPE##_##HASH##_##EQ##_should_shrink(ctl_hashset_##TYPE##_##HASH##_##EQ* ht) { \
  return ht->size == (size_t)((double)ht->bucket_size * CTL_HASH_SHRINK_RATIO); \
} \
QUAL size_t _ctl_hashset_##TYPE##_##HASH##_##EQ##_hash(const ctl_hashset_##TYPE##_##HASH##_##EQ* ht, TYPE value) { \
  return HASH##_##TYPE(value) % ht->bucket_size; \
} \
QUAL ctl_res_void _ctl_hashset_##TYPE##_##HASH##_##EQ##_rehash(ctl_hashset_##TYPE##_##HASH##_##EQ* ht, ctl_hashset_##TYPE##_##HASH##_##EQ##_node** old_buckets, size_t old_bucket_size) { \
  ctl_res_void res = {0}; \
  res.ec = EOK; \
  ctl_hashset_##TYPE##_##HASH##_##EQ##_node* node = NULL; \
  ctl_hashset_##TYPE##_##HASH##_##EQ##_node* next = NULL; \
  size_t new_idx = 0U; \
  size_t bucket_idx = 0U; \
  for (bucket_idx = 0U; bucket_idx < old_bucket_size; bucket_idx++) { \
    node = old_buckets[bucket_idx]; \
    while (node) { \
      next = node->next; \
      new_idx = _ctl_hashset_##TYPE##_##HASH##_##EQ##_hash(ht, node->value); \
      node->next = ht->buckets[new_idx]; \
      ht->buckets[new_idx] = node; \
      node = next; \
    } \
  } \
  return res; \
} \
QUAL ctl_res_void _ctl_hashset_##TYPE##_##HASH##_##EQ##_resize(ctl_hashset_##TYPE##_##HASH##_##EQ* ht, size_t new_bucket_size) { \
  ctl_res_void res = {0}; \
  res.ec = EOK; \
  ctl_hashset_##TYPE##_##HASH##_##EQ##_node** old = NULL; \
  size_t old_bucket_size = 0U; \
  if (new_bucket_size < CTL_HASH_MININAL_CAPACITY) { \
    if (ht->bucket_size > CTL_HASH_MININAL_CAPACITY) { \
      new_bucket_size = CTL_HASH_MININAL_CAPACITY; \
    } else { \
      return res; \
    } \
  } \
  old = ht->buckets; \
  old_bucket_size = ht->bucket_size; \
  CHECK_EXEC_RES_RET_RES(_ctl_hashset_##TYPE##_##HASH##_##EQ##_allocate(ht, new_bucket_size), res, res); \
  _ctl_hashset_##TYPE##_##HASH##_##EQ##_rehash(ht, old, old_bucket_size); \
  free(old); \
  return res; \
} \
QUAL size_t ctl_hashset_##TYPE##_##HASH##_##EQ##_size(ctl_hashset_##TYPE##_##HASH##_##EQ* ht) { \
  return ht->size; \
} \
ctl_res_void ctl_hashset_##TYPE##_##HASH##_##EQ##_ctor_with_capacity(ctl_hashset_##TYPE##_##HASH##_##EQ* ht, size_t capacity) { \
  ht->size = 0U; \
  return _ctl_hashset_##TYPE##_##HASH##_##EQ##_allocate(ht, capacity); \
} \
QUAL ctl_res_ctl_hashset_##TYPE##_##HASH##_##EQ##_p ctl_hashset_##TYPE##_##HASH##_##EQ##_new_with_capacity(size_t capacity) { \
  ctl_res_ctl_hashset_##TYPE##_##HASH##_##EQ##_p res = {0}; \
  res.ec = EOK; \
  ctl_hashset_##TYPE##_##HASH##_##EQ* ht = (ctl_hashset_##TYPE##_##HASH##_##EQ*)malloc(sizeof(ctl_hashset_##TYPE##_##HASH##_##EQ)); \
  CHECK_COND_RET_RES(ht != NULL, EOOM, res); \
  ctl_hashset_##TYPE##_##HASH##_##EQ##_ctor_with_capacity(ht, capacity); \
  res.value = ht; \
  return res; \
} \
QUAL ctl_res_void ctl_hashset_##TYPE##_##HASH##_##EQ##_ctor(ctl_hashset_##TYPE##_##HASH##_##EQ* ht) { \
  return ctl_hashset_##TYPE##_##HASH##_##EQ##_ctor_with_capacity(ht, CTL_HASH_MININAL_CAPACITY);  \
} \
QUAL ctl_res_ctl_hashset_##TYPE##_##HASH##_##EQ##_p ctl_hashset_##TYPE##_##HASH##_##EQ##_new() { \
  return ctl_hashset_##TYPE##_##HASH##_##EQ##_new_with_capacity(CTL_HASH_MININAL_CAPACITY); \
} \
QUAL ctl_res_void ctl_hashset_##TYPE##_##HASH##_##EQ##_dtor(ctl_hashset_##TYPE##_##HASH##_##EQ* ht) { \
  ctl_res_void res = {0}; \
  res.ec = EOK; \
  ctl_hashset_##TYPE##_##HASH##_##EQ##_node* node = NULL; \
  ctl_hashset_##TYPE##_##HASH##_##EQ##_node* next = NULL; \
  size_t idx = 0U; \
  for (idx = 0U; idx < ht->bucket_size; idx++) { \
    node = ht->buckets[idx]; \
    while (node) { \
      next = node->next; \
      _ctl_hashset_##TYPE##_##HASH##_##EQ##_free_node(node); \
      node = next; \
    } \
  } \
  free(ht->buckets); \
  return res; \
} \
QUAL ctl_res_void ctl_hashset_##TYPE##_##HASH##_##EQ##_copy(ctl_hashset_##TYPE##_##HASH##_##EQ* dst, ctl_hashset_##TYPE##_##HASH##_##EQ* src) { \
  ctl_res_void res = {0}; \
  res.ec = EOK; \
  CHECK_COND_RET_RES(dst, ENULLPTR, res); \
  ctl_hashset_##TYPE##_##HASH##_##EQ##_node* node = NULL; \
  size_t idx = 0U; \
  ctl_hashset_##TYPE##_##HASH##_##EQ##_dtor(dst); \
  _ctl_hashset_##TYPE##_##HASH##_##EQ##_allocate(dst, src->bucket_size); \
  for (idx = 0; idx < dst->bucket_size; idx++) { \
    node = src->buckets[idx]; \
    while (node) { \
      _ctl_hashset_##TYPE##_##HASH##_##EQ##_push_front(dst, idx, node->value); \
      node = node->next; \
    } \
  } \
  return res; \
} \
QUAL ctl_res_void ctl_hashset_##TYPE##_##HASH##_##EQ##_free(ctl_hashset_##TYPE##_##HASH##_##EQ* ht) { \
  ctl_res_void res = {0}; \
  res.ec = EOK; \
  CHECK_COND_RET_RES(ht, ENULLPTR, res); \
  CHECK_EXEC_RES_RET_RES(ctl_hashset_##TYPE##_##HASH##_##EQ##_dtor(ht), res, res); \
  free(ht); \
  return res; \
} \
QUAL ctl_res_ctl_hashset_##TYPE##_##HASH##_##EQ##_iter ctl_hashset_##TYPE##_##HASH##_##EQ##_get(const ctl_hashset_##TYPE##_##HASH##_##EQ* ht, TYPE value) { \
  ctl_res_ctl_hashset_##TYPE##_##HASH##_##EQ##_iter res = {0}; \
  ctl_hashset_##TYPE##_##HASH##_##EQ##_iter iter = {0}; \
  iter.node = NULL; \
  ctl_hashset_##TYPE##_##HASH##_##EQ##_node* node = NULL; \
  ctl_hashset_##TYPE##_##HASH##_##EQ##_node* prev = NULL; \
  size_t idx = _ctl_hashset_##TYPE##_##HASH##_##EQ##_hash(ht, value); \
  node = ht->buckets[idx]; \
  while (node) { \
    if (EQ##_##TYPE(value, node->value)) { \
      iter.bucket_idx = idx; \
      iter.bucket_size = ht->bucket_size; \
      iter.node = node; \
      res.value = iter; \
      return res; \
    } \
    prev = node; \
    node = node->next; \
  } \
  res.ec = ENOTFOUND; \
  res.value = iter; \
  return res; \
} \
QUAL ctl_res_void _ctl_hashset_##TYPE##_##HASH##_##EQ##_grow(ctl_hashset_##TYPE##_##HASH##_##EQ* ht) { \
  return _ctl_hashset_##TYPE##_##HASH##_##EQ##_resize(ht, ht->size * CTL_HASH_GROW_FACTOR); \
} \
QUAL ctl_res_void ctl_hashset_##TYPE##_##HASH##_##EQ##_put(ctl_hashset_##TYPE##_##HASH##_##EQ* ht, TYPE value) { \
  ctl_res_void res = {0}; \
  res.ec = EOK; \
  CHECK_COND_RET_RES(ht != NULL, ENULLPTR, res); \
  if (_ctl_hashset_##TYPE##_##HASH##_##EQ##_should_grow(ht)) { \
    _ctl_hashset_##TYPE##_##HASH##_##EQ##_grow(ht); \
  } \
  size_t idx = _ctl_hashset_##TYPE##_##HASH##_##EQ##_hash(ht, value); \
  ctl_hashset_##TYPE##_##HASH##_##EQ##_node* node = ht->buckets[idx]; \
  while (node) { \
    if (EQ##_##TYPE(value, node->value)) { \
      TYPE##_copy(&(node->value), &value); \
      return res; \
    } \
    node = node->next; \
  } \
  _ctl_hashset_##TYPE##_##HASH##_##EQ##_push_front(ht, idx, value); \
  ht->size++; \
  return res; \
} \
QUAL ctl_res_void _ctl_hashset_##TYPE##_##HASH##_##EQ##_shrink(ctl_hashset_##TYPE##_##HASH##_##EQ* ht) { \
  return _ctl_hashset_##TYPE##_##HASH##_##EQ##_resize(ht, (size_t)((double)ht->size * CTL_HASH_SHRINK_RATIO)); \
} \
QUAL ctl_res_void ctl_hashset_##TYPE##_##HASH##_##EQ##_remove_by_iter(ctl_hashset_##TYPE##_##HASH##_##EQ* ht, ctl_hashset_##TYPE##_##HASH##_##EQ##_iter iter) { \
  ctl_res_void res = {0}; \
  res.ec = EOK; \
  CHECK_COND_RET_RES(iter.node != NULL, ENULLPTR, res); \
  const size_t bucket_idx = iter.bucket_idx; \
  ctl_hashset_##TYPE##_##HASH##_##EQ##_node* bucket_node = ht->buckets[bucket_idx]; \
  ctl_hashset_##TYPE##_##HASH##_##EQ##_node* prev = NULL; \
  ctl_hashset_##TYPE##_##HASH##_##EQ##_node* node = iter.node; \
  while (bucket_node) { \
    if (node == bucket_node) { \
      if (prev) { \
        prev->next = node->next; \
      } else{ \
        ht->buckets[bucket_idx] = node->next; \
      } \
      _ctl_hashset_##TYPE##_##HASH##_##EQ##_free_node(node); \
      ht->size--; \
      if (_ctl_hashset_##TYPE##_##HASH##_##EQ##_should_shrink(ht)) { \
        _ctl_hashset_##TYPE##_##HASH##_##EQ##_shrink(ht); \
      } \
      return res; \
    } \
    prev = bucket_node; \
    bucket_node = bucket_node->next; \
  } \
  res.ec = ENOTFOUND; \
  return res; \
} \
QUAL ctl_res_void ctl_hashset_##TYPE##_##HASH##_##EQ##_remove(ctl_hashset_##TYPE##_##HASH##_##EQ* ht, TYPE value) { \
  ctl_res_void res = {0}; \
  res.ec = EOK; \
  ctl_hashset_##TYPE##_##HASH##_##EQ##_node* node = NULL; \
  ctl_hashset_##TYPE##_##HASH##_##EQ##_node* prev = NULL; \
  size_t idx = _ctl_hashset_##TYPE##_##HASH##_##EQ##_hash(ht, value); \
  node = ht->buckets[idx]; \
  while (node) { \
    if (EQ##_##TYPE(value, node->value)) { \
      if (prev) { \
        prev->next = node->next; \
      } else { \
        ht->buckets[idx] = node->next; \
      } \
      _ctl_hashset_##TYPE##_##HASH##_##EQ##_free_node(node); \
      ht->size--; \
      if (_ctl_hashset_##TYPE##_##HASH##_##EQ##_should_shrink(ht)) { \
        _ctl_hashset_##TYPE##_##HASH##_##EQ##_shrink(ht); \
      } \
      return res; \
    } \
    prev = node; \
    node = node->next; \
  } \
  res.ec = ENOTFOUND; \
  return res; \
}

#define IMPL_HASHSET(TYPE, HASH, EQ) IMPL_QUAL_HASHSET(TYPE, HASH, EQ, )
#define IMPL_STATIC_HASHSET(TYPE, HASH, EQ) IMPL_QUAL_HASHSET(TYPE, HASH, EQ, static)
#define IMPL_INLINE_STATIC_HASHSET(TYPE, HASH, EQ) IMPL_QUAL_HASHSET(TYPE, HASH, EQ, inline static)
#endif